home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / RedBlackKeyTree.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  2.7 KB  |  148 lines  |  [TEXT/CWIE]

  1. // RedBlackKeyTree.cp
  2.  
  3. #ifndef RedBlackKeyTree_h
  4. #include "RedBlackKeyTree.h"
  5. #endif
  6. #ifndef RedBlackKey_h
  7. #include "RedBlackKey.h"
  8. #endif
  9. #ifndef ElementNotFound_h
  10. #include "ElementNotFound.h"
  11. #endif
  12.  
  13. template < class Key >
  14. RedBlackKey<Key> *RedBlackKeyTree<Key>::DownCast( NodeBase *n )
  15.   {
  16.     return static_cast< Node* >( n );
  17.   }
  18.  
  19. template < class Key >
  20. const RedBlackKey<Key> *RedBlackKeyTree<Key>::DownCast( const NodeBase *n )
  21.   {
  22.     return static_cast< const Node* >( n );
  23.   }
  24.  
  25. template < class Key >
  26. void RedBlackKeyTree<Key>::Remove( Node& node )
  27.   {
  28.     TreeBase::Remove( node );
  29.   }
  30.  
  31. template < class Key >
  32. void RedBlackKeyTree<Key>::Add( Node& node )
  33.   {
  34.     if ( IsEmpty() )
  35.       {
  36.         TreeBase::Add( node, atRoot );
  37.         return;
  38.       }
  39.  
  40.     Node *position = Root();
  41.     
  42.     while ( true )
  43.         if ( node >= *position )
  44.           {
  45.             if ( position->HasRightChild() )
  46.                 position = position->Right();
  47.              else
  48.               {
  49.                 TreeBase::Add( node, after, *position );
  50.                 return;
  51.               }
  52.           }
  53.          else
  54.           {
  55.             if ( position->HasLeftChild() )
  56.                 position = position->Left();
  57.              else
  58.               {
  59.                 TreeBase::Add( node, before, *position );
  60.                 return;
  61.               }
  62.           }
  63.   }
  64.  
  65. template < class Key >
  66. RedBlackKey<Key> *RedBlackKeyTree<Key>::FindTopmost( const Key& k ) const
  67.   {
  68.     Node *position = const_cast<Node *>( Root() );
  69.     while ( position != 0 && *position != k )
  70.         if ( *position > k )
  71.             position = position->Left();
  72.          else
  73.             position = position->Right();
  74.     
  75.     return position;
  76.   }
  77.  
  78. template < class Key >
  79. RedBlackKey<Key>& RedBlackKeyTree<Key>::Lookup( const Key& k ) const
  80.   {
  81.     Node *position = FindTopmost( k );
  82.     if ( position == 0 )
  83.         throw ElementNotFoundAt<Key>( k );
  84.     return *position;
  85.   }
  86.  
  87. template < class Key >
  88. RedBlackKey<Key> *RedBlackKeyTree<Key>::FindFirst( const Key& k ) const
  89.   {
  90.     Node *result = FindTopmost( k );
  91.     
  92.     if ( result == 0 )
  93.         return 0;
  94.     
  95.     Node *position = result->Left();
  96.     
  97.     while ( position != 0 )
  98.         if ( *position == k )
  99.           {
  100.             result = position;
  101.             position = position->Left();
  102.           }
  103.          else
  104.             position = position->Right();
  105.     
  106.     return result;
  107.   }
  108.  
  109. template < class Key >
  110. RedBlackKey<Key> *RedBlackKeyTree<Key>::FindLast( const Key& k ) const
  111.   {
  112.     Node *result = FindTopmost( k );
  113.     
  114.     if ( result == 0 )
  115.         return 0;
  116.     
  117.     Node *position = result->Right();
  118.     
  119.     while ( position != 0 )
  120.         if ( *position == k )
  121.           {
  122.             result = position;
  123.             position = position->Right();
  124.           }
  125.          else
  126.             position = position->Left();
  127.     
  128.     return result;
  129.   }
  130.  
  131. template < class Key >
  132. bool RedBlackKeyTree<Key>::Valid() const
  133.   {
  134.     if ( !TreeBase::Valid() )
  135.         return false;
  136.     
  137.     const Node *n = First();
  138.     while ( n != 0 )
  139.       {
  140.         const Node *next = n->Next();
  141.         if ( next != 0 && *next < *n )
  142.             return false;
  143.         n = next;
  144.       }
  145.     
  146.     return true;
  147.   }
  148.